package org.example;

import java.util.LinkedList;

public class Solution11 {

    public int[] maxSlidingWindow(int[] nums, int k) {

        // 检查输入的有效性
        if (nums == null || nums.length == 0 || k <= 0) {
            return new int[0];
        }

        int resIndex = 0;

        // 结果数组
        int[] result = new int[nums.length - k + 1];

        // 双端队列，用于存储窗口内的元素索引
        LinkedList<Integer> deque = new LinkedList<>();

        // 遍历数组
        for(int i = 0; i < nums.length; i++) {

            // 滑动窗口的范围是从 i - k + 1 到 i (包括两端)
            // 移除超出窗口范围的索引
            while(!deque.isEmpty() && deque.peekFirst() < i - k + 1 ) {
                deque.pollFirst();
            }

            // 删除所有比新入队列小的元素
            while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
                deque.pollLast();
            }

            // 将当前的索引添加到队列的尾部
            deque.offerLast(i);

            // 当窗口的大小为k时记录最大值
            if (i >= k - 1) {
                result[resIndex++] = nums[deque.peekFirst()];
            }

        }

        return result;
    }

}
